package class04_归并排序.test;

/**
 * 求一个数组中的逆序对
 */
public class Code03_ReversePair {
    public static int reverPairNumber(int[] arr){
        if(arr == null || arr.length < 2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int L, int R) {
        if(L == R){
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(arr, L, mid)
                + process(arr, mid + 1, R)
                + merge(arr, L, mid, R);
    }

    private static int merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int p1 = mid;
        int p2 = R;
        int index = 0;
        int reversePair = 0;
        while (p1 >= L && p2 >= mid + 1){
            if(arr[p1] > arr[p2]){
                reversePair += p2 - mid;
            }
            help[index++] = arr[p1] <= arr[p2] ? arr[p2--] : arr[p1--];
        }
        while (p1 >= L){
            help[index++] = arr[p1--];
        }
        while (p2 >= mid + 1){
            help[index++] = arr[p2--];
        }
        for (int i = 0; i < help.length; i++) {
            arr[i + L] = help[help.length - 1 - i];
        }
        return reversePair;
    }

    public static void main(String[] args) {
        int testTime = 500000;
        int maxValue = 100;
        int maxSize = 100;
        boolean secceed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generataRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            if(reverPairNumber(arr1) != comparator(arr2)){
                secceed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
            printArray(arr1);
            printArray(arr2);
        }

        System.out.println(secceed?"Good!":"Fuck!!");
    }

    private static void printArray(int[] arr1) {
        if(arr1 == null){
            return;
        }
        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + " ");
        }
        System.out.println();
    }

    private static int comparator(int[] arr) {
        if(arr == null) {
            return 0;
        }
        int reversePair = 0;
        for (int i = arr.length - 1; i >= 0 ; i--) {
            for (int j = 0; j < i; j++) {
                if(arr[j] > arr[i]){
                    reversePair ++;
                }
            }
        }
        return reversePair;
    }

    private static int[] copyArray(int[] arr) {
        if(arr == null) {
            return new int[0];
        }
        int[] arr2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[i];
        }
        return arr2;
    }

    private static int[] generataRandomArray(int maxSize, int maxValue) {
        int size = (int)(Math.random() * (1 + maxSize));
        int[] help = new int[size];
        for (int i = 0; i < size; i++) {
            help[i] = (int)(Math.random() * (1 + maxValue));
        }
        return help;
    }
}
